package com.computer.fundamentals.algorithm;

/**
 * 贪心算法定义：
 * 1. 在对问题求解时，总是做出在当前看来是最好的选择。
 * 2. 不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解
 *
 * 贪心算法的使用条件：
 * 1. 一个问题的整体最优解可通过一系列局部的最优解的选择达到，并且每次的选择可以依赖以前作出的选择，
 *    但不依赖于后面要作出的选择。这就是贪心选择性质。对于一个具体问题，要确定它是否具有贪心选择性质，
 *    必须证明每一步所作的贪心选择最终导致问题的整体最优解
 * 2. 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心法求解的关键所在。
 *
 */
public class GreedyMethod {

    /**
     * 贪心策略——以经典问题 加油站 为例(LeetCode.134):
     * ------------------------------------------------------------------------------------------------------------
     * 在一条环路上有N个加油站，其中第i个加油站有汽油gas[i]升.
     * 你有一辆油箱容量无限的的汽车,从第i个加油站开往第i+1个加油站需要消耗汽油cost[i]升.你从其中的一个加油站出发,开始时油箱为空。
     *
     * 如果你可以绕环路行驶一周,返回出发时加油站的编号,否则返回 -1。
     *
     * 说明：
     * 如果题目有解，该答案即为唯一答案。
     * 输入数组均为非空数组，且长度相同。
     * 输入数组中的元素均为非负数。
     * ------------------------------------------------------------------------------------------------------------
     */
    public int canCompleteCircuit(int[] gas, int[] cost) {
        // 事实上只需要关心剩余油量的最低值在何处即可得到最终的答案
        // 因为如果说可以跑完一圈，那么按照贪心策略，在最低点度过后一定会使得油量补充回来（不用管后续的变化细节）
        // 因此在保证油量总数足够的前提下，答案即为最低点后的第一个加油站
        int res = -1; // 起始点下标
        int minSpare = Integer.MAX_VALUE; // 最低剩余量
        int spare = 0; // 累计油量
        for (int i = 0;i < gas.length;i++) {
            spare += gas[i] - cost[i];
            if (spare < minSpare) {
                minSpare = spare;
                res = i;
            }
        }

        return spare < 0 ? -1 : (res+1) % gas.length;
    }

    /**
     * 测试,可以前往 https://leetcode-cn.com/problems/gas-station/ 进行详细的测试
     */
    public static void main(String[] args) {

        GreedyMethod greedyMethod = new GreedyMethod();
        System.out.println("------------测试------------");
        int res = greedyMethod.canCompleteCircuit(new int[]{1, 2, 3, 4, 5}, new int[]{3, 4, 5, 1, 2});
        System.out.println(res);

    }
}